package com.wang.violentrecursion;

import java.util.LinkedList;

/**
 * @Author: along
 * @Create: 2021/9/2
 * @Description:
 */
public class Demo13_AllLessNumSubArray {
    public static int getNum(int[] arr, int num) {
        if(arr == null || arr.length == 0) {
            return 0;
        }
        LinkedList<Integer> qMax = new LinkedList<>();
        LinkedList<Integer> qMin = new LinkedList<>();
        int L = 0;
        int R = 0;
        //[L...R) -> 左闭右开 若[2,2) 认为窗口内无数
        int res = 0;
        //L为窗口的开头位置 尝试每一个开头位置
        while (L < arr.length) {
            //如果此时窗口开头为L while循环 直到R右扩到窗口违规
            while (R < arr.length) {
                while (!qMin.isEmpty() && arr[qMin.peekLast()] >= arr[R]) {
                    qMin.pollLast();
                }
                qMin.addLast(R);
                //R -> arr[R]
                while (!qMax.isEmpty() && arr[qMax.peekLast()] <= arr[R]) {
                    qMax.pollLast();
                }
                qMax.addLast(R);
                //一旦发现不达标 直接break
                if (arr[qMax.getFirst()] - arr[qMin.getFirst()] > num) {
                    break;
                }
                R++;
            }
            res += R - L;
            //R是最后一个达标位置的下一个 即第一个违规的位置
            if (qMin.peekFirst() == L) {
                qMin.pollFirst();
            }
            if (qMax.peekFirst() == L) {
                qMax.pollFirst();
            }

            L++;
        }

        return res;
    }

}
